[이코테-그리디]_1이 될 때까지
💯 solving-algo | March 23, 2021
1이 될 때까지 - My Solution
n, k = map(int, input().split())
cnt = 0
while n != 1:
if n % k == 0:
cnt += 1
n /= k
else:
cnt += 1
n -= 1
print(cnt)- N를 1로 만드는 최적의 해를 찾는 문제로 최대한 많이 나눌 수 있는 것을 중점적으로 계산하면 되었다.
이코테 - 풀이 1
n, k = map(int, input().split())
result = 0
# n이 k 이상이라면 k로 계속 나누기
while n >= k:
# n이 k로 나누어 떨어지지 않는다면 n에서 1씩 빼기
while n % k != 0:
n -= 1
result += 1
# k로 나누기
n //= k
result += 1
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
n -= 1
result += 1
print(result)이코테 - 풀이2
n, k = map(int, input().split())
result = 0
# n를 k의 배수로 만들기
while n % k != 0:
target = (n // k) * k
result += n - target
n = target
# k로 더이상 나눌 수 없을 때
if n < k:
break
result += 1
n //= k
#마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)- 1씩 빼주는 연산의 범위가 커지면 시간 복잡도에서 시간 초과가 날 수 있으므로,
- k로 나누어 떨어지는 n으로 만들어 불필요한 -1 연산을 빠르게 빼주었다.
